Например, Бобцов

Кластеризация аппроксимированного Парето-фронта

Аннотация:

Введение. В современной инженерной и научно-технической практике многокритериальная оптимизация часто обеспечивает поиск компромиссных решений без задания весовых коэффициентов и границ, формируя Парето-фронт посредством эвристической аппроксимации на основе генетических алгоритмов. Однако даже аппроксимированный Парето-фронт представляет собой множество точек, что затрудняет анализ и отбор решений. Для упорядочения и структурирования полученных решений возможным решением становится кластеризация, позволяющая выделить репрезентативные группы компромиссов. Научная новизна предлагаемого метода кластеризации заключается в комбинации алгоритмов Ordering Points to Identify the Clustering Structure и k-means с выделением медоидов, обеспечивающей автоматическое удаление шума и компактное представление репрезентативных стратегий. Метод. Предложен метод двухэтапной кластеризации. На первом этапе применен алгоритм Ordering Points to Identify the Clustering Structure, с помощью которого строится упорядоченный профиль плотности и автоматически фильтруются шумовые точки по порогу досягаемости. На втором этапе использован алгоритм k-means, выполнено разбиение отфильтрованного ядра Парето-фронта на кластеры и вычислены центроиды, а затем медоиды — реальные представители данных. Основные результаты. Проведены два эксперимента на трехмерных множествах точек Парето-фронта (1226 и 2514 ядровых точек после фильтрации). В результате применения предложенной методики получено разбиение на 10 кластеров. Установлено, что после фильтрации доля шумовых точек составила менее 1 % от общего числа решений. Фильтрация позволяет существенно снизить значения метрики, оценивающей качество центров кластеров, при умеренном увеличении суммарного времени выполнения кластеризации. Показано, что малая рассогласованность центроидов и соответствующих медоидов свидетельствует о высокой репрезентативности полученных кластеров. Обсуждение. Предложенный комбинированный метод, сочетающий применение алгоритмов Ordering Points to Identify the Clustering Structure и k-means, требует настройки двух параметров, автоматически адаптируется к нелинейным плотностям и размерам входных данных. Область применения метода может быть расширена для любых задач многокритериальной оптимизации, решаемых посредством построения и анализа Парето-фронта, включая инженерную оптимизацию, логистику, энергетику и финансовое моделирование. В перспективе возможно внедрение адаптивных методов для автоматического определения оптимальных параметров используемых алгоритмов, а также обеспечения адаптации к динамическим изменениям многокритериальных задач.

Ключевые слова:

Постоянный URL

Статьи в номере

Содержание © 1993–2026 Университет ИТМО
Разработка © 2015 Университет ИТМО